Technology using an “index”, a piece of data generated for a set of data, is known. By using an index, it becomes easy to search a data set from which the index is generated for a piece of data having intended attributes.
Typical search methods by use of an index include a keyword search and a scope search. The scope search will be particularly considered here. In the case of carrying out a scope search on normal data which are not encrypted, a simple comparison in small-and-large relation suffices; any specific method is not necessary.
When data are encrypted as a countermeasure against divulging of information, comparison in small-and-large relation of original data using an encrypted text encrypted with a general encryption method is not possible. PTLs 1 to 5, for example, disclose technologies in which a database is created after data to be stored are encrypted, keywords that are search keys are encrypted, and so on. By encrypting data as disclosed in the literatures, divulging of information from encrypted messages can be prevented. However, carrying out a scope search on data encrypted with these technologies is not possible.
To carry out a scope search on encrypted data, another technology is thus needed.
In the description below, a technology for carrying out search processing on data while encrypting the data is described in detail.
NPL 1 discloses an encryption method by which a plain text can be encrypted while a numerically small-and-large relation in the text is maintained. The method described in NPL 1, however, has a drawback that order information itself is divulged from an encrypted message.
By the technologies using indexes, disclosed in NPL 2 and NPL 3, not only divulging of information from encrypted texts is prevented but also divulging of information from the indexes can be prevented.